package mydsl;

import java.util.Arrays;
import java.util.List;

public class BinaryTreeBuilder {
    /**
     * 从宽度遍历顺序构造二叉树
     */
	public static <E> void BTFromLevelOrder(BinaryTree<E> tree, List<E> list) {
		if(list.size() > 0) {
			tree.addRoot(list.get(0));
			build((BTNode<E>)tree.root(), list, 0);
		}
	}
    
	private static <E> void build(BTNode<E> node, List<E> values, int index) {
		node.setElement((E)values.get(index));
        if (index * 2 + 1 < values.size()) {
        	node.setLeft(new BTNode(values.get(index * 2 + 1)));
        	build(node.getLeft(), values, index * 2 + 1);
        }
        if (index * 2 + 2 < values.size()) {
        	node.setRight(new BTNode(values.get(index * 2 + 2)));
        	build(node.getRight(), values, index * 2 + 2);
        }
    }
	
	// Construct Tree from given Inorder and Preorder traversals
	/**
	 * 
	 * Let us consider the below traversals:
	 * Inorder sequence: D B E A F C
	 * Preorder sequence: A B D E C F
	 * In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.
     *            A
     *          /   \
     *        /       \
     *      D B E     F C
     * We recursively follow above steps and get the following tree.
     *        A
     *      /   \
     *     /     \
     *    B        C
     *   / \       /
     *  /   \     /
     * D     E   F

	 * Algorithm: buildTree()
	 * 1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
	 * 2) Create a new tree node tNode with the data as picked element.
	 * 3) Find the picked element’s index in Inorder. Let the index be inIndex.
	 * 4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
	 * 5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
	 * 6) return tNode.
	 */
	
	static int preIndex = 0;

	
	/* Recursive function to construct binary of size len from
	   Inorder traversal in[] and Preorder traversal pre[].  Initial values
	   of inStrt and inEnd should be 0 and len -1.  The function doesn't
	   do any error checking for cases where inorder and preorder
	   do not form a tree */
	private static BTNode<Character> buildTree(char in[], char pre[], int len, int inStrt, int inEnd) {
	  if(inStrt > inEnd)
	     return null;
	 
	  /* Pick current node from Preorder traversal using preIndex
	    and increment preIndex */
	  BTNode<Character> tNode = new BTNode<Character>(pre[preIndex++]);
	 
	  /* If this node has no children then return */
	  if(inStrt == inEnd)
	    return tNode;
	 
	  /* Else find the index of this node in Inorder traversal */
	  int inIndex = search(in, inStrt, inEnd, tNode.element());
	 
	  /* Using index in Inorder traversal, construct left and
	     right subtress */
	  tNode.setLeft(buildTree(in, pre, len, inStrt, inIndex-1));
	  tNode.setRight(buildTree(in, pre, len, inIndex+1, inEnd));
	 
	  return tNode;
	}
	
	private static int search(char arr[], int strt, int end, char value) {
		int i;
		for(i = strt; i <= end; i++) {
			if(arr[i] == value)
			return i;
		}
		return i;	
	}

	public static void main(String[] args) {
//		BinaryTreeBuilder.BTFromLevelOrder(tree, Arrays.asList(1,2,3,4,5,6,7,8));
		
		char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};
		char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};
		int len = in.length;
//		LinkedBinaryTree<Character> tree = new LinkedBinaryTree<Character>(BinaryTreeBuilder.buildTree(in, pre, len, 0, len-1));
//		BTNode<Character> root = (BTNode<Character>) tree.root();
//		root = BinaryTreeBuilder.buildTree(in, pre, len, 0, len - 1);
//		System.out.println(root);
//		System.out.println(tree.root());
//		System.out.println(tree.toString(tree.iteratorLevelOrder()));
//		System.out.println(tree);
	}
}
